package Algorithm.dynamicProgramming.introduct;

/**
 * 121. 买卖股票的最佳时机 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock
 * 题目简述：给定一个数组prices ，它的第i个元素prices[i]表示股票第i天的价格。你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。计算所能获取的最大利润。
 */
public class MaxProfit {

    /**
     * 思路一：从左向右扫描，记录已扫描区间最小值low，并计算当前价格与其差值然后更新利润，最后更新low，再继续向后扫描。
     */
    public int maxProfit(int[] prices) {
        if (prices.length < 2) return 0;
        int low = prices[0], result = 0;
        for (int i = 1;i < prices.length;i++) {
            //计算与前面的最小值low的差值用于更新利润
            result = Math.max(result, prices[i] - low);
            //更新已扫描区间最小值lo
            low = Math.min(low, prices[i]);
        }
        return result;
    }

    /**
     * 动态规划
     * 1. 定义dp: dp[i][0]为第i天不持有股票最多现金，dp[i][1]为第i天持有股票最多现金
     * 2. 状态转移公式：第i天不持有股票这个状态可由第i-1天不持有股票或第i天卖出股票这两个状态得来，故dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
     *               第i天持有股票这个状态可由第i-1天持有股票或第i天买入股票这两个状态得来，故dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
     * 3. 初始化：dp[0][0] = 0;dp[0][1] = -prices[0];
     * 4. 递推的过程中获取最大的dp[i][0]。仔细体会状态这个概念
     */
    public int maxProfit2(int[] prices) {
        int[][] dp = new int[prices.length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        int max = dp[0][0];
        for(int i = 1;i < prices.length;i++) {
            //若不持有股票
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
            //若持有股票
            dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
            //最后一定是不持有股票时的现金最多
            max = Math.max(max, dp[i][0]);
        }
        return max;
    }
}
